1. Technical Field
The invention is related to shift-correction encoding systems which correct shift errors in data received from a channel by encoding the data prior to its transmission through the channel after it has been channel encoded. Such shift-correction encoding systems are disclosed in U.S. patent application Ser. No. 07/200,166 filed May 31, 1988 by Dennis George Howe, Edward Joseph Weldon and Hugh Michael Hilden entitled SHIFT-CORRECTING CODE FOR CHANNEL ENCODED DATA and assigned to the assignee of the present application (hereinafter referred to as the referenced patent application).
2. Background Art
The referenced patent application discloses a system in which shift errors in run-length-limited (RLL) channel encoded data are corrected using a shift-correction code system operating "inside" the RLL channel encoder/decoder system. RLL encoded data comprises a succession of "runs" of successive binary zeroes, adjacent runs being separated by a binary one. The value of each run is the number of zeroes in the corresponding run (or alternatively, one plus that number). Such RLL data is constrained in that the number of zeroes in each run must be at least d and no more than k, so that the RLL data is said to be (d,k)-constrained.
Briefly, the shift-correction code system encodes successive blocks, (one at a time) of RLL channel encoded data by appending to each block a check block of redundant (parity) RLL data prior to transmission of the data through a channel (e.g., recording of the data in a storage system). The check data is computed from a sequence of message symbols drawn from GF(p), where p is a prime number. These message symbols are computed from the contigious runs which comprise the input block of RLL data by first transforming each run into a cumulative sum of the values of all preceding runs in the block. This first transformation prevents individual shift errors in data transmitted through the channel from affecting more than one symbol of the shift-correction coded data block, which is a requirement of such shift-correction codes (which requirement will be referred to herein after as the "shift-correction-condition"). Then, each sum value is reduced modulo p, where the value p determines the type of shift errors which can be corrected by the shift-correction code. (In the usual case p=3, and the resulting ternary code symbols, which are called "trits", have as their value either +1, -1 or 0). The result of these operations is the representation of the input block of channel data as a block of elements drawn from an alphabet of cardinality p (ie., from GF[p]).
The message block of Galois field symbols thus generated is then encoded in accordance with a suitable code over GF(p.sup.m) (where m is a non-zero integer) to generate a corresponding block of redundant check symbols. The check symbols are then transformed to binary data which conforms to the (d,k) constraints of the RLL channel code. It is this last transformation to which the present invention is directed.
This binary data is then appended to the original message RLL channel data as the redundant "check" channel data. When such shift-correction encoded blocks of channel data are received from the channel, a shift-correction decoder detects the presence of any shift errors introduced by the channel into the data by simply inspecting the syndrome of the received shift-correction coded data block and may correct such errors using error locator and error evaluator polynomials in accordance with well-known techniques.
In essence, if p=3 a one bit shift in the position of a binary one separating two adjacent runs of zeroes in the RLL channel encoded data received from the channel is detected by the presence of a trit of value either+1 or -1 in the error evaluator polynomial of the affected codeword, depending upon whether the shift was a "forward" shift or a "backward" shift. By adding this non-zero trit value to the appropriate trit in the codeword and then transforming the codeword back to RLL-constrained binary data, the correct RLL data sequence is produced in which the binary one which was originally shifted is restored to its correct position. Alternatively, since each element of the error evaluator polynomial corresponds uniquely to a particular run in the RLL data received from the channel, shift error correction could be done directly by appropriately shifting "ones" corresponding to non-zero elements of the error evaluator polynomial.
Problem to be solved by the Invention
In what follows, we shall assume p=3; the shift correction code symbols are thus "trits". As mentioned above, after the block of redundant check symbols (in the form of "trits") have been computed from the message trits representing the input block of RLL channel-encoded data, the check symbols--parity trits--must be transformed into RLL binary data in order that they may be appended to the input message RLL channel encoded data and transmitted with it through the channel. As described in the above-referenced patent application, this process is fraught with several significant problems. First, depending upon the value of the last bit in the block of original input RLL channel encoded data and the value of the first bit in the block of redundant RLL data, simply catenating the two blocks together may cause a violation of the (d,k) constraints of the RLL channel code. In order to avoid violating these constraints, a set of link bits may be interposed between the "message" block of the original RLL channel-encoded data and the "check" block of redundant RLL data. These link bits must be carefully computed in accordance with the last several (e.g., two) bits of the message block, as described on page 22 of the above-referenced patent application. Furthermore, since the present "check" block is immediately followed by the next "message" block in the RLL data stream sent to the channel, another violation of the RLL (d,k) constraints must be guarded against by placing another set of link bits at the end of each RLL encoded check block.
In the case when the shift-correction encoded blocks of channel data are to be of fixed length, obtaining the link bits is particularly problematical because of the complex considerations entailed in their computation. For example, generating check blocks of uniform length (in terms of RLL bits) as described in the above-referenced patent application at page 25 lines 6 through 33, involves several computational steps. First, each redundant parity trit s' generated by the shift-correction encoder must be transformed in accordance with the inverse of the cumulative sum transformation mentioned above. In the inverse transformation, each trit s' is treated as if it were a cumulative sum of values of the preceding and current RLL runs x' reduced modulus p. The inverse transformation obtains the value of each current RLL run x'. This run is then converted to a binary sequence x by assigning run values d, d+1 and d+2 to x' values of 0, 1 and -1, respectively. Then, the number of channel bits comprising the binary sequences x representing all of the redundant parity trits of the current block must be computed. (This number is simply the cumulative number of zeroes in the binary RLL representation of the check block plus the number of ones separating successive run symbols.)
This result is subtracted from the desired length of the check block; the difference is the number of link bits (binary zeroes) that are to be appended to the binary RLL representation of the current check block of redundant parity symbols. If the number of these link bits is too large (e.g., if the total number of zeroes in the last run of the check block is greater than k), then another RLL run symbol must be appended to the check block.
This entire process, particularly the inverse transformation from s' symbols to x' symbols, is time consuming and/or requires hardware investment
Another problem is that the shift-correction decoder must locate and discard the link bits before decoding. Otherwise, it will misdecode. Since the number of link bits at the end of each check block changes with the content of the data, tracking and locating the link bits is a computational task and represents overhead in both operational time and dedicated hardware.
Another limitation of the methods taught in the above-referenced patent application concerns coding rate. The aggregate number of channel bits required to represent each redundant check block as a uniform (fixed) length RLL bit sequence conforming to the RLL code's (d,k) constraints is quite large relative to the number of bits that would correspond to the theoretical maximum encoding rate between trit symbols and RLL (d,k)-constrained binary symbols. To demonstrate this, we consider the coding of trits to (2,7)-constrained binary sequences. The maximum theoretical rate at which this can be accomplished is R=log.sub.3 (1.431).apprxeq.0.326.apprxeq.8/25 trits/bit. In the example on page 25 of the above-referenced patent application, a "shift-correction-condition" compliant encoding scheme is disclosed in which four parity trits are represented by 22 channel bit long (2,7)-constrained sequences, a coding rate of 4/22. To the extent that these coding rates are lower than the theoretical maximum coding rate for such a transformation, they represent a limitation on system performance.
It is an object of the invention to provide a shift-correction condition compliant method for transforming a sequence of parity trits into a fixed length binary RLL sequence which automatically obeys specified (d,k) constraints.
It is a further object of the invention that the binary RLL sequence thus formed can be spliced into an arbitrary location in a d,k-constrained binary sequence without the use of link bits and without requiring the inverse transformation from the trit symbols s' to the binary symbols x' to effect shift correction encoding. This feature requires less computation and simpler hardware to implement.
It is a yet further object of the invention to accomplish this while achieving a high shift-correction code rate.